Obeleži sve kategorije koje odgovaraju problemu

Карактери и ниске

Елементи програмског језика

Опишимо мало детаљније како се могу представити подаци текстуалног типа у програму. Текст се представља у облику ниске (engl. string) која се састоји од карактера.

У језику C++ је најбољи избор да користимо податак типа string (из заглавља <string>), јер тада на располагању имамо многе библиотечке операције и функције (већина су методе класе string).

Постоји могућност да се уместо података типа string користи низ карактера (низ елемената типа char) у коме се за ознаку краја користи карактер чији је ASCII кôд нула (за такве ниске се каже да су терминисане завршном нулом, односно, на енглеском језику null terminated strings). Тај начин рада са текстом је типичан за програмски језик C и много га је теже користити него рад са типом string, тако да га у решењима задатака у овој збирци нећемо користити.

Константне ниске се записују између двоструких наводника. На пример,

string s = "Zdravo svima";

Ниску која садржи једно или више појављивања неког карактера можемо добити на следећи начин.

string s(5, 'a');  // s sadrži tekst "aaaaa"

Ако је str променљива типа string, наредба cin >> str; учитава једну реч са стандардног улаза (до позиције прве белине, занемарујући белине на почетку речи). Све речи, до краја улаза, можемо учитавати на следећи начин:

string rec;
while (cin >> str)
  ...

Други начин да се ово постигне јесте да се употреби итератор улазног тока.

istream_iterator<string> pocetak(cin), kraj;
for (auto it = pocetak; it != kraj; it++) {
   string rec = *it;
   ...
}

Наредбом getline(cin, str); се у ниску str учитава цела линија текста (текст до преласка у нови ред или до краја улаза). Прелазак у нови ред се не смешта у ниску str. Функција враћа вредност која се када се употреби унутар услова наредбе while или if аутоматски конвертује у вредност true ако је читање било успешно тј. вредност false ако није (то се дешава ако се пре покушаја читања дошло до краја улаза). Тако се читање линија до краја улаза може остварити са:

string str;
while (getline(cin, str))
   ...

У заглављу <string> декларисано је мноштво метода помоћу којих се може радити са нискама (објектима типа string). Најважније су следеће:

• size, length – враћа дужину ниске тј. број њених карактера;
• find, rfind – враћа позицију првог тј. последњег појављивања неког карактера или подниске унутар ниске тј. специјалну вредност string::npos ако тражени карактер или подниска не постоје;
• substr – издваја подниску дате ниске, као параметре прихвата позицију на којој почиње подниска која се издваја и дужину подниске. Ако се не наведе дужина подниске, издваја се подниска која почиње на задатој позицији и протеже се до краја ниске;
• replace – мења део ниске другом ниском;
• insert – умеће ниску на дату позицију унутар друге ниске;
• erase – из текуће ниске брише се њена подниска која почиње на задатој позицији и задате је дужине.

Две ниске се могу надовезати коришћењем оператора + и резултат је нова ниска. Проширивање ниске неким суфиксом (додавање текста на њен десни крај) се може вршити оператором +=. Нагласимо да проширивање наредбом облика str += s може бити знатно ефикасније него наредбом облика str = str + s, јер се у другој понекад прво креира нова ниска у коју се копира садржај ниске str и ниске s, након чега би се тај нови садржај додељује ниски s, што доводи до велике неефикасности (ово је чувени пример лошег решења у програмирању познато под именом Schlemiel the Painter’s algorithm).

Подаци типа string имају двојако тумачење. Са једне стране можемо их сматрати елементарним, атомичким подацима (на пример, видели смо да се могу “сабирати”, слично бројевима). Са друге стране ниске се могу третирати и као колекције (низови) карактера и над њима је могуће спроводити исте алгоритме које смо спроводили над низовима и векторима. На пример, иако је s објекат типа string, а не низ или вектор, изразом s[i] може се одредити његов i-ти карактер (под претпоставком да је i мање од дужине ниске). Методама begin и end, односно истоименим функцијама могуће је добити итераторе на почетак и непосредно изнад краја ниске, које је могуће проследити функцијама које обрађују опсеге. На пример, sort(s.begin(), s.end()) сортира све карактере ниске s (у абецедном поретку). Такође, кроз све карактере ниске могуће је проћи петљом облика

for (char c : str)
   ...

Карактери и ниске

Елементи програмског језика

Опишимо мало детаљније како се могу представити подаци текстуалног типа у програму. Текст се представља у облику ниске (engl. string) која се састоји од карактера.

Основни тип података за представљање текста тј. ниски у језику C# је string. На пример, функција Console.ReadLine() која учитава целу линију текста враћа податак типа string. Константне ниске наводе се између двоструких наводника (за разлику од карактера који се наводе између једноструких), на пример, "zdravo". Пошто језик C# подржава скуп карактера Unicode, ниске могу да садрже све наше латиничне и ћириличне карактере.

Подаци типа string имају двојако тумачење. Са једне стране можемо их сматрати елементарним, атомичким подацима. Већ смо видели да се, веома слично као бројеви, подаци типа string се могу “сабирати” тј. надовезивати коришћењем оператора +. Иако се не могу поредити релацијским операторима, њихово лексикографско поређење је веома једноставно помоћу метода String.CompareTo.

Тип string подржава разне библиотечке методе (при чему су неке идентичне као за низове или листе). Најважније су следеће:

• Substring – издваја део ниске тј. подниску. Аргументни позива могу бити почетна позиција и број карактера који се издвајају. Ако се други аргумент изостави, тада се издвајају карактери од наведене позиције, па све до краја ниске.
• IndexOf — врши претрагу ниске (било тако што се тражи карактер или подниска). Враћа позицију првог појављивања или вредност -1, ако тражени карактер или подниска не постоје. Метода LastIndexOf је веома слична, али враћа позицију последњег појављивања.
• Split — врши поделу ниске на делове и враћа низ података типа string.

Са друге стране, својство Length које одређује дужину ниске и оператор индексног приступа (на пример, s[i]), при чему се индекси броје од нуле, чини их веома сличним низовима карактера. Слично као и код низова, итерацију кроз све карактере ниске можемо извршити помоћу петље foreach. Ипак, постоји једна јако важна разлика између низова карактера и података типа string – подаци типа string се не могу мењати (кажемо да су ниске имутабилне). Имутабилност има озбиљне последице на ефикасност, јер у неким ситуацијама програми због тога могу бити бржи, а некада могу бити прилично спорији. На пример, сабирање две ниске обавезно проузрокује креирање треће ниске и копирање садржаја сабирака у резултат, што је прилично неефикасно, нарочито ако се често понавља у програму. Зато уместо података типа string у неким ситуацијама за рад са текстом морамо користити друге типове података.

Ако желимо да мењамо појединачне карактере (али не и дужину ниске), тада можемо радити са класичним низом карактера (типа char[]). Податак типа string се једноставно конвертује у низ карактера (методом ToCharArray или методом ToArray из библиотеке Linq), док се низ карактера може конвертовати у string позивом конструктура new string(...) (обратимо пажњу да се у оба случаја алоцира нова меморија и да ове конверзије трају одређено време).

У ситуацијама када се врши често надовезивање велике количине текста или често брисање и замена делова текста, уместо типа string можемо користити тип StringBuilder. Ако се конструише без наведених аргумената креће се од празног текста. Ако се приликом конструкције наведе аргумент типа string, тада StringBuilder иницијално садржи исти текст као наведени string. Слично листама, овај тип омогућава да се текст проширује (користи се метода Append). Уклањање делова текста може се вршити методом Remove, а замена методом Replace. Податак типа StringBuilder се може директно исписати помоћу Console.WriteLine, а може се превести у string позивом метода ToString.